class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==1){
            return nums[0];
        }
        int sum=nums[0];
        int max=nums[0];
        for(int i=1;i<nums.size();i++){
            sum=sum+nums[i]>nums[i]?sum+nums[i]:nums[i];
            max=max>sum?max:sum;
        }
        return max;

    }
};

//town 2020.8.14 
// 简化版本
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int sum=nums[0];
        int max_sum=nums[0];
        int pre=nums[0];
        for(int i=1;i<nums.size();i++){
            sum=max(pre+nums[i],nums[i]);
            pre=sum;
            max_sum=max(max_sum,sum);
        }
        return max_sum;        
    }
};

// sum[i] 代表以nums[i]结尾区间最大的和
// sum[i]=max(sum[i-1]+nums[i],nums[i])
// 数组版本
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> sum(nums.size(),0);
        sum[0]=nums[0];
        int max_sum=INT_MIN;
        for(int i=1;i<nums.size();i++){
            sum[i]=max(sum[i-1]+nums[i],nums[i]);
            max_sum=max(max_sum,sum[i]);
        }
        return max_sum;
    }
};